17.5 マルチバージョンコピー法

17.4で紹介したレプリケーションコピーGC(Nettles and O’Toole［1993］)では、グローバルなストップザワールド同期でミューテータスレッドすべてをto 空間に遷移させる必要があった

flip

ロックフリーな並行コピーGCが欲しい

各スレッドごとにflipできるようにしたい

マルチバージョンコピー法 Herlhy and Moss［1992］の概要

ここでのプロセッサはスレッドのことだと思えばよい

Haslstead方式 (アルゴリズム17-1)で必要になるグローバル同期を取り除くため、Herlihy とMoss はfrom 空間の回収とflip を切り離した

ここに突然Halsteadの話が入ってくるので読みにくい

Halstead はflipに必要なグローバルな同期はそのまま残して、全プロセッサにto 空間への反転（flip）を行わせてからfrom 空間を捨てるようにした。

各プロセッサ用領域を1 つのto 空間と複数（ゼロ個以上）のfrom 空間に分割した

各プロセッサには走査中に見つけたfrom空間オブジェクトを自分のto空間に移動させる責任がある

コピーが進むにつれ、1 つのオブジェクトに関する複数のfrom 空間バージョンが、それぞれ異なる空間に作られていく

正確には最新のto空間バージョンがどんどん作られるので結果としてfrom空間バージョンが複数できる

それぞれのプロセッサが勝手にflipするので、from空間にあるオブジェクトを他のプロセッサが見ている可能性がある

from空間にあるオブジェクトを見ているというのは問題を引き起こしそう

実は各オブジェクトから最新のものまで辿れるようになっている

それらのバージョンのうち、ただ1 つのオブジェクトだけが現行版(to空間にあるもの)で、残りはもはや使わない旧バージョンである

各プロセッサ内でのGCの流れ

個々のプロセッサは、ミューテータタスクと走査タスクを交互に実行する

よしなに切り替えるのかな?

mallocのタイミングとか

オンザフライインクリメンタルGCということになる (p372)

走査タスクではローカル変数とto 空間をチェックしてfrom 空間バージョンへのポインタを探す

そのようなポインタが見つかると、スキャナはオブジェクトの現行版の場所を調べる

nextをたどっていけばできる(後述)

もし現行版がいずれかのfrom 空間にあれば、スキャナはオブジェクトをto 空間へコピーし、それを新たな現行版とする

つまり、プロセッサAのfrom空間にあったオブジェクトがプロセッサBのto空間に移動することがあり得る

各プロセッサの義務と責任

各プロセッサは協調してオブジェクトをfrom 空間からto 空間へ移し、到達可能なポインタをto 空間へ向けて書き換える

各プロセッサの責務は、自分のto 空間を走査してfrom 空間へのポインタを探し、見つけたfrom 空間オブジェクト（他のプロセッサのfrom 空間のオブジェクトも含む）で、まだどのプロセッサのto 空間にも現行版がないものをコピーすることである

プロセッサは、ミューテータタスクを実行中ならば、（to 空間がいっぱいで、新たなto 空間を割り付けられるだけの空きスペースがある場合）いつでもto 空間とfrom 空間を反転して良いが、走査中に反転を行ってはならない

ここがレプリケーションコピーGCとの違い

ロックフリーにするために重要

from 空間を解放する際には、他のどのプロセッサも自分のfrom 空間オブジェクトへの参照を保持していないことを確認しなければならない(後述)

オブジェクトのバージョン管理

バージョンを管理するため、Herlihy とMoss は転送ポインタフィールドnext を常に全オブジェクトに持たせ、from 空間の旧バージョンが次のバージョンを指し、最後の現行バージョンではnull を転送ポインタとして入れておくようにした

from 空間オブジェクトを自分のto 空間へコピーする際、走査しているプロセッサはto 空間コピーをバージョン連鎖の最後に、CompareAndSwap を使って不可分に接続し、現行バージョンとする。

したがって、ミューテータがアクセスする際には必ずバージョンの連鎖を最後までたどってからアクセス動作を実行しなければならない

また、ロックフリー性を保ち、同時に、ヒープへの更新が失われないことを保証するため、オブジェクトへのストアの際には、そのオブジェクトの新しいバージョンを、ミューテータ動作をしているプロセッサのto 空間に作り、CompareAndSwap を用いて現行版とする。

プロセスAがオブジェクトOを頻繁に書き換えた場合、Oのかつてのバージョンが大量にAのto空間に残される

永続データ構造をイメージすると良い

このように、走査やコピーにはグローバルな同期を必要とせず、また、ミューテータによる更新が失われることもない。

From空間の破棄

from 空間を所有しているプロセッサ（オーナ）がfrom 空間を破棄してよいのは、他の走査中のプロセッサ（スキャナ）がどれも、自分のfrom 空間へのポインタを保持していない時だけである。

あるオーナに関して走査がクリーンであるとは、走査が完了しても、そのオーナの持つどのfrom空間のバージョンに対するポインタも見つからなかったことを指す

すなわち、走査してもto空間へのポインタしか見つからない場合に、クリーンであるという

そうでない場合、すなわちfrom空間へのポインタが見つかる場合に、ダーティであるという

全from空間を一度に捨てることしか考えていないように見える

この点については後で言及がある

ラウンドとは、全プロセッサが走査を開始してから終了するまでの間をいう。

この定義はわかりにくい

ラウンドは各プロセッサについて定義され、flipから次のflipまでの間

クリーンなラウンドとは、全プロセッサの走査がクリーンで、どのプロセッサもflip を行わなかったラウンドをいう

任意のfrom 空間はクリーンなラウンドの後で回収可能となる

オーナとスキャナの同期

そもそもなぜハンドシェークが必要なのか?

あるオーナに関して走査がクリーンであることを表現するため

あるスキャナが走査している間にオーナがflipすると、to空間に存在すると判断していたオブジェクトがfrom空間に移動してダーティになる

flipを行うとto空間がfrom空間になる

スキャナのto空間またはローカル変数からfrom空間へのポインタが存在することになるのでダーティである

ダーティをクリーンにするためには、スキャンをやりなおさなければならない

オーナは、他のスキャナの走査開始と終了を、2 つの不可分なハンドシェークビットを用いて検知する。

2つのビットそれぞれは、片方のプロセッサが読み出し、もう一方のプロセッサが書き込む。

オーナ → スキャナに情報を伝達するビット

スキャナ → オーナに情報を伝達するビット

初期状態では、双方のビットが一致している。

flip を開始するには、オーナが新しいto 空間を生成し、古いto 空間にfrom空間であるという印をつけ、自分のハンドシェークビットを反転する

双方のビットが一致しているときにのみflipを開始できる

走査開始時にスキャナはオーナのハンドシェークビットを読み、走査を実行し、自分のハンドシェークビットをオーナから読んだ値にセットする。

したがって、2 つのハンドシェークビットは、スキャナが走査を開始して終了するまでの間にオーナがflipしなければ再び一致することになる。

複数のオーナとスキャナ

しかし、オーナはすべてのプロセスが走査を開始し、終了したことを検知しなければならず、また、すべてのプロセッサは対称で、スキャナでもオーナでもある。

そこで、ハンドシェークビットは2 つの配列として表現する。

code:hand_shake.cpp

std::array<bool, N> owner;

オーナ配列はオーナのハンドシェークビットを格納しており、オーナプロセッサ番号を添字とする。

2 次元のスキャナ配列はスキャナのハンドシェークビットを格納し、各スキャナ‒オーナの組に対応する要素を持つ。

1 つの走査が完了すると複数のオーナに対して通知する必要があるため、スキャナはオーナ配列全体をローカルな配列に、走査のたびにコピーしなければならない。

code:scan.cpp

auto local_copy = owner;

scan();

走査が終了すると、スキャナは自分に対応するスキャナビットを以前に保存した値にセットする。

オーナは、自分のオーナビットが全スキャナのビットと一致すればラウンド終了を検知する。

全スキャナビットの一致がラウンドの境界になる

flipによってオーナビットが変化することで、次のラウンドが始まる

現在のラウンドが完了するまで、オーナは(flipできないので)新たなラウンドを始めることができない。

ラウンドのクリーン/ダーティ判定

完了したラウンドがクリーンであったかどうかを判定するには、プロセッサが共有するダーティビットの配列を用いる。

この配列は、プロセッサ番号によって添字付けられている。

code:dirty.cpp

std::array<bool, N> dirty;

オーナがflip を実行すると、オーナは他の全プロセッサのダーティビットをセットする。

code:set.cpp

for (auto i = 0; i < N; ++i) {

if (i != owner_id) {

}

}

また、スキャナが他のプロセッサのfrom 空間へのポインタを発見すると、スキャナはそのプロセッサのダーティビットをセットする。

もし、あるオーナのダーティビットがラウンドの終わりにクリアされていれば、そのラウンドはクリーンであり、そのオーナの持つすべてのfrom 空間を回収できる。

さもなければ、オーナはただダーティビットをクリアし、新たな走査を開始する。

ダーティビットをプロセッサでなくfrom 空間に対応させ、スキャナがポインタを発見した際にターゲットのfrom 空間のダーティビットをセットするようにすれば、from 空間すべてをいっぺんに回収するかわりに、1 つずつ個別に回収できるようになる。

「全from空間を一度に捨てることしか考えていないように見える」への回答

安全性と活性

Herlihy とMoss は自分たちのアルゴリズムの安全性と活性を証明した

安全性（safety）: コレクタは、少なくともすべての到達可能なオブジェクトが失われないよう維持しなければならない。

活性（liveness）: コレクタは、最終的にGC サイクルを完了しなければならない。

彼らの活性に関する議論の根拠は、もし全プロセッサがいずれは必ず走査を行うならば、いずれかのプロセッサがいつかは必ず自己のfrom 空間を回収するという事実である。

最悪の場合、全プロセッサがいずれ空き領域を使い果たし、それ以上flip ができなくなり、全プロセッサがやがては走査処理に集中することとなり、クリーンなラウンドが起こることになる

もちろん、このような資源の枯渇は、システム全体をブロックしてしまうという結果をもたらす

コピーオンライトを避けるための拡張

このマルチバージョンアルゴリズムの新規性は、完全にロックフリーであるという点である。

欠点は、ヒープの書き換えのたびに新バージョンを作らなければならない点である（ただし、この点は非均一なメモリアクセス（NUMA）のマルチプロセッサにおける局所性を改善する上で役立つ可能性はある）。

CompareAndSwap2 を用いた上書き更新

最初の拡張は、CompareAndSwap2 命令が使えることを仮定している。

これどんな命令?

アルゴリズム13-12 (p. 297)を参照

2つの変数を同時にチェックして2つとも期待する値をもっていたら書き換える

この命令は、書き換えを実行し、同時に、転送ポインタnext がnull のままであることを保証できる不可分命令である。

code: cas2.py

def write(src, i, ref):

残念ながら、CompareAndSwap2 を実装している現在の(いつ？)マルチプロセッサはそれほど多くない。

CompareAndSwapを用いた上書き更新

オブジェクトa のヘッダに対していくつかフィールドを追加する必要がある

seq(a) は、2 を法とする連番

index(a) は書き換えようとしているスロットのインデックス

value(a) はそのスロットの新しい値である

転送ポインタフィールドnext(a) には、ポインタやnull に加えて連番の値も保持できるようにする (下位ビットを使う?)

連番には2 つの値だけあればよい。

もし seq(a) == next(a) ならば、現在の書き換えをインストールし、そうでなければ無視する。

CompareAndSwapを用いた上書き更新 (2)

完全なライトバリアを用いてストアを実行するには、プロセッサはバージョンのリストをたどって最新版（null か連番がnext フィールドに入っているバージョン）を見つける

もし最新版がローカルならば、プロセッサはアルゴリズム17‒3 に示したWriteLocal 操作を実行する

code:WriteLocal.py

def WriteLocal(a, next, i, v):

seq ← (next + 1) % 2 $ #

# seq(a) ← 1 でも動きそう

seq(a) ← seq

index(a) ← i

value(a) ← v

# next フィールドに新しい値をインストールしようとする。

# CompareAndSet(&next(a), next, seq) == false なら WriteLocalを呼び出してからここに来るまでに

# next(a)の書き換えが行われたということになる

# Q: 書き換えが2度行われると一致してしまう?

# A: 書き換え中にリモートが割り込んだ場合は、nextが異なるので問題ない

# ローカルで2度書き換えた場合は、CompareAndSetが成功するので問題ない

# ただし、seqをインクリメンタルに変化させる意味がどれほどあるかはわからない

if CompareAndSet(&next(a), next, seq)

# もし成功すれば、プロセッサは削除バリアを実行してストア操作が上書きするポインタを走査し

# その後、ストアを実行する

else

# プロセッサはより新しいバージョンを探し、完全なライトバリアを実行して、更新を再試行する

Write(a, i, v)

def CompareAndSet(p: pointer to int, old: int, new: int):

if *p ≠ old

return false

*p ← new

return true

CompareAndSwapを用いた上書き更新 (3)

もしオブジェクトがリモートならば、新たなオーナがローカルなto 空間コピーを以前に述べたとおりに作成する。

異なる点は、コピーを生成してからストアを実行するまでにnext(a)=seq(a) かどうかをチェックしなければならないという点である。

もしこの2 つが等しければ、ペンディングになっている更新をまず実行しなければならないので、新オーナはバリアを実行してインデックスフィールドが示すスロットを走査し、値フィールドから値をスロットにストアする。

まったく同じ処理を、スキャナがオブジェクトをto 空間に脱出させる際にも行わなければならない

この処理によって、オリジナルオブジェクトに対してコピー中に行われたすべての書き込みが、コピーに対して実行された書き込みより前に線形化される。

ここの記述はなにかおかしい

ロックを用いた上書き

1. CompareAndSwap を用い、ロック中であることを示す特別な値をnext フィールドに書き込んでロック。

2. ストアが上書きするポインタを（もしあれば）走査。

3. 書き換えを実行。

4. ストアされるポインタを（もしあれば）走査。

5. next にnull を書き直してオブジェクトをアンロック。